class code1 {
    //实现一个字典树

    class TrieNode{
        boolean val;
        TrieNode[] child = new TrieNode[26];
    }
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    public void insert(String word) {
        TrieNode p = root;
        for(char c:word.toCharArray()) {
            int t = c - 'a';

            if(p.child[t] == null) p.child[t] = new TrieNode();

            p = p.child[t];
        }
        p.val = true;
    }

    public boolean search(String word) {
        TrieNode p = root;
        for(char c:word.toCharArray()) {
            int t = c - 'a';

            if(p.child[t] == null) return false;

            p = p.child[t];
        }
        return p.val;
    }

    public boolean startsWith(String prefix) {
        TrieNode p = root;
        for(char c:prefix.toCharArray()) {
            int t = c - 'a';

            if(p.child[t] == null) return false;

            p = p.child[t];
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */